Messages transmitted over a wireless medium are encoded in order to reduce the chances that noise will corrupt the message. The encoding translates an original block of an original message which comprises a plurality of bits which are either ‘0’ or ‘1’ to an encoded block which is formed of a plurality of symbols which are either ‘0’ or ‘1’. The encoding of the block usually includes adding redundancy (i.e., making the encoded block longer than the original block), introducing symbol dependency (i.e., making the value of each symbol in the encoded block a function of a plurality of bits in the original block) and interleaving the block (i.e., mixing the order of the symbols in the encoded block). In modern codes the size of the original block is usually very large, of the order of hundreds, thousands or tens of thousands of bits. Thus, the encoding turns a block of binary bits into a block of binary symbols. It is noted that there is not necessarily a direct correlation between the value of a single bit and the value of any one of the encoded symbols. However, the number of bits in the original block and the number of symbol groups in the encoded block are generally the same. Generally in convolutional codes, bits and symbol groups in corresponding locations within the block are related in that they form pairs of input and output of encoders and decoders, as described hereinbelow.
In convolutional codes, an encoder which has a fixed number of possible states is used to encode the original block. Each bit of the original block which enters the encoder changes a current state of the encoder to a next state according to the value of the entering bit. It is noted that for convolutional codes, from each state the encoder can move only to two other states based on whether the input is ‘0’ or ‘1’. For each entering bit the encoder generates a group of one or more symbols forming the transmitted message. In other trellis codes, larger inputs are received by the encoder in each iteration, and the number of possible state changes are larger accordingly. In decoding, the decoder assigns each state a state metric (SM), which represents the conditional probability that the encoder was in that state.
During transmission of the message, noise is added to the transmitted encoded message, and a decoder is used to extract the original message from the received message, which includes the noise. Normally, each symbol in the received message is represented in the receiver, before decoding, by a word which represents the chance that the symbol is a logical ‘1’. A high positive value of the word means that the symbol is a logical ‘1’ with high confidence, while a negative value with a high absolute value means the symbol is a logical ‘0’ with high confidence. A word with a zero value means that the symbol is a ‘0’ or ‘1’ with equal probability. This representation is referred to herein as soft data.
Some decoding methods include one or more iterations of a step of an A-Posteriori probability estimation in which the soft data representation of each symbol is adjusted and/or represented by a hard value (i.e., either ‘0’ or ‘1’) based on the values of other symbols in the block of the adjusted symbol.
Many methods for performing the adjustment step are based on the Bahl algorithm which is described, for example, in Steven S. Pietrobon, “Implementation and Performance of a Turbo/MAP Decoder”, Int. J. Satellite Commun, vol. 16, pp. 23-46, January -February 1998, the disclosure of which is incorporated herein by reference. In the Bahl algorithm, for each received symbol group, two vectors of state metrics are prepared; a forward vector which represents the conditional probability of the encoder being in each of the possible states immediately before the symbol group was generated and a backward vector which represents the conditional probability of the encoder being in each of the possible states immediately after the symbol group was generated. The forward vector is calculated based on the received symbols which precede the adjusted symbol group in the block and the backward vector is calculated based on the received symbols which follow the adjusted symbol group in the block. The forward and backward vectors are recursively dependent on the previous state metric vector in the respective directions from the end points of the block.
The forward and backward vectors of each symbol group are supplied concurrently to a log likelihood ratio (LLR) unit which provides an adjusted output value of the symbol group based on the forward and backward vectors and the original value of the symbol group. The output value is chosen according to the most likely transitions between the state metrics of the forward and backward vectors.
After the vectors are supplied to the LLR unit, the vectors may be discarded unless they are needed for calculating vectors of other symbol groups. Therefore, it is preferred, in order to save storage, that the vectors be calculated immediately before they are used. However, due to the recursive nature of the vectors which are calculated from opposite sides of the block, such immediate calculation, usage and discarding is performed in the prior art only in one direction, e.g., in the forward direction.
A conventional prior art method for calculating the output values of all the symbols in a block comprises two passes over the block. In a first pass over the block, performed before the LLR unit begins the adjusting, the backward recursion vectors for all the symbols in the block are calculated and stored. In a second pass over the block, beginning from the opposite end of the block, the forward recursion vectors are calculated, the respective backward recursion vectors are retrieved from the storage and the forward and backward vectors are supplied to the LLR unit. The supplied vectors are immediately used by the LLR unit and then they are discarded.
The storage requirements in this method, required in order to store the backward recursion vectors, are quite large. In order to reduce the required storage space, it has been suggested to perform the symbol adjustments in sub-blocks in which each symbol is influenced only by the symbols in its sub-block, rather than by all the symbols in the block. Such method is described, for example, in PCT publication WO98/20617 the disclosure of which is incorporated herein by reference. The WO98/20617 publication shows that by beginning the recursion calculations from a point sufficiently before the beginning of the sub-block, the recursion values corresponding to the symbols in the sub-block are sufficiently valid although the recursion did not start from the beginning of the block. Even so, the storage requirements for a 16-state code, using 10-bit state metrics for blocks of 40 symbols, is 6400 bits. When implementing a hardware decoder such an amount of storage is very expensive.
FIG. 1A is an exemplary trellis map 10 of the convolutional code 7.5 which is known in the art. The encoder of the 7.5 code may be in any of four states s(n) 12 identified by a combination of two bits. From each of the states s(n), the encoder can move to one of two other states s(n+1) based on an input bit d(n), as indicated by branches 14. In moving from state s(n) to state s(n+1) 16, the encoder provides a symbol group formed of a pair of bits c0(n) and c1(n). The symbol group c0(n) and c1(n) is transmitted to a receiver which uses a decoder to determine the original bits d(n). The decoder assigns each received symbol group with a vector of branch metric (BM) values δn(c0,c1) which designate the conditional probability that the received symbol group originates from the transmitted symbol group designating c0 and c1. In addition, the decoder calculates forward (αn) and backward (βn) state metric vectors which have elements for each of the states s(n) which designate the conditional probability that the decoder was in the state s(n) at time n. Generally, forward vectors αn are recursively dependent on preceding vectors (αn+1=f(αn, δn)), and backward vectors βn are recursively dependent on following vectors (βn=f(βn+1, δn)).
As can be seen in FIG. 1A, Each pair of states s(n) is connected to a pair of states s(n+1) although not necessarily the same states. The pairs of states with the connecting branches form a butterfly trellis which is depicted in FIG. 1B which is a butterfly trellis diagram for convolutional codes. This feature of pairs of states is generally true in trellises of convolutional codes. In FIG. 1A states 00 and 01 (which are equivalent to states X and Y in FIG. 1B) at time n are connected to states 00 and 10 (which are equivalent to states Z and W in FIG. 1B) at time n+1. Similarly, states 10 and 11 at time n (which are equivalent to states X and Y in FIG. 1B) are connected to states 01 and 11 at time n+1 (equivalent to states Z and W in FIG. 1B).